package com.zwj.interview.堆;


import java.util.*;

/**
 * 请找出数组中出现频率最高的k个数字。例如，当k等于2时，输入数组[1，2，2，1，3，1]，
 * 由于数字1出现了3次，数字2出现了2次，数字3出现了1次，因此出现频率最高的2个数字是1和2
 */
public class TopK {

    /**
     * 在用哈希表统计完数组中每个数字的频率之后，再逐一扫描哈希表中每个从数字到频率的映射，
     * 以便找出频率最高的k个数字。如果最小堆中元素的数目小于k，则直接将从数字到频率的映射添加到最小堆中。
     * 如果最小堆中已经有k个元素，那么比较待添加数字的频率和位于堆顶的数字的频率。
     * 如果待添加的数字的频率低于或等于堆顶的数字的频率，那么堆中的k个数字的频率都比待添加的数字的频率高，
     * 它不可能是k个频率最高的数字中的一个，可以忽略。如果待添加的数字的频率高于堆顶的数字的频率，
     * 那么删除堆顶的数字（最小堆中频率最低的数字），并将待添加的数字添加到最小堆中
     *
     * @param nums
     * @param k
     * @return
     */
    public List<Integer> topFrequent(int[] nums, int k) {
        /**
         * 哈希表numToCount用来统计数字出现的频率，它的键是数组中的数字，值是数字在数组中出现的次数。
         * 最小堆minHeap中的每个元素是哈希表中从数字到频率的映射。由于最小堆比较的是数字的频率，
         * 因此调用构造函数创建minHeap设置的比较规则是比较哈希表中映射的值，也就是数字的频率
         */
        Map<Integer, Integer> numToCount = new HashMap<>();
        for (int num : nums) {
            numToCount.put(num, numToCount.getOrDefault(num, 0) + 1);
        }
        //传入比较规则
        Queue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((e1, e2) -> e1.getValue() - e2.getValue());
        for (Map.Entry<Integer, Integer> entry : numToCount.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);  //小于k的时候添加
            } else {
                if (entry.getValue() > minHeap.peek().getValue()) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }
            }
        }

        List<Integer> result = new LinkedList<>();
        for (Map.Entry<Integer, Integer> entry : minHeap) {
            result.add(entry.getKey());
        }
        //如果说需要返回int[]的话，可以使用兰姆达表达式
        //int[] res = result.stream().mapToInt(Integer::intValue).toArray();
        return result;
    }

    public static void main(String[] args) {
        System.out.println(new TopK().topFrequent(new int[]{4, 1, -1, 2, -1, 2, 3}, 2));
    }



}
